|
In graph theory, a connected dominated set and a maximum leaf spanning tree are two closely related structures defined on an undirected graph. ==Definitions== A connected dominating set of a graph ''G'' is a set ''D'' of vertices with two properties: #Any node in ''D'' can reach any other node in ''D'' by a path that stays entirely within ''D''. That is, ''D'' induces a connected subgraph of ''G''. #Every vertex in ''G'' either belongs to ''D'' or is adjacent to a vertex in ''D''. That is, ''D'' is a dominating set of ''G''. A minimum connected dominating set of a graph ''G'' is a connected dominating set with the smallest possible cardinality among all connected dominating sets of ''G''. The connected domination number of ''G'' is the number of vertices in the minimum connected dominating set.〔.〕 Any spanning tree ''T'' of a graph ''G'' has at least two leaves, vertices that have only one edge of ''T'' incident to them. A maximum leaf spanning tree is a spanning tree that has the largest possible number of leaves among all spanning trees of ''G''. The max leaf number of ''G'' is the number of leaves in the maximum leaf spanning tree.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Connected dominating set」の詳細全文を読む スポンサード リンク
|